// network_characteristics.js

export function computeNetworkCharacteristics(nodes, edges) {
    const nodeIds = nodes.map(n => n.id);
    const nodeIdSet = new Set(nodeIds);
    const nodeCount = nodes.length;
    const edgeCount = edges.length;
  
    // 1. 平均度数: 2 * 边数 / 点数
    const averageDegree = (2 * edgeCount) / nodeCount;
  
    // 2. 构建邻接表
    const adj = new Map();
    for (const id of nodeIds) {
      adj.set(id, []);
    }
    for (const [from, to] of edges) {
      if (adj.has(from)) adj.get(from).push(to);
      if (adj.has(to)) adj.get(to).push(from);
    }
  
    // 3. 简化版介数中心性：通过 BFS 统计每个节点位于多少对节点最短路径中
    const centrality = new Map();
    for (const id of nodeIds) {
      centrality.set(id, 0);
    }
  
    for (let s = 0; s < nodeCount; s++) {
      const start = nodeIds[s];
      const queue = [start];
      const visited = new Set([start]);
      const paths = new Map();
      paths.set(start, []);
  
      // BFS 建立最短路径树
      while (queue.length > 0) {
        const current = queue.shift();
        for (const neighbor of adj.get(current)) {
          if (!visited.has(neighbor)) {
            visited.add(neighbor);
            queue.push(neighbor);
            paths.set(neighbor, [...(paths.get(current) || []), current]);
          }
        }
      }
  
      // 对所有可达目标节点，回溯路径上的中间点
      for (const [target, path] of paths.entries()) {
        if (target !== start && path.length > 1) {
          for (const intermediate of path.slice(0, -1)) {
            centrality.set(intermediate, centrality.get(intermediate) + 1);
          }
        }
      }
    }
  
    // 4. 平均介数中心性（可不归一化）
    const avgBetweenness =
      Array.from(centrality.values()).reduce((a, b) => a + b, 0) / nodeCount;
  
    return {
      nodeCount,
      edgeCount,
      averageDegree,
      averageBetweenness: avgBetweenness,
    };
  }
  